import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class Solution301 {
    /**
     * 删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
     *
     * 说明: 输入可能包含了除 ( 和 ) 以外的字符。
     *
     * 示例 1:
     *
     * 输入: "()())()"
     * 输出: ["()()()", "(())()"]
     * 示例 2:
     *
     * 输入: "(a)())()"
     * 输出: ["(a)()()", "(a())()"]
     * 示例 3:
     *
     * 输入: ")("
     * 输出: [""]
     *
     */
    public List<String> removeInvalidParentheses(String s) {
        HashSet<String> set = new HashSet<>();
        int idx = 0;
        int leftToDelete = 0;
        int rightToDelete = 0;
        int leftCount = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '('){
                leftToDelete++;
            }else if (c == ')') {
                if (leftToDelete > 0){
                    leftToDelete--;
                }else {
                    rightToDelete++;
                }
            }
        }
        dfs(s, idx, leftCount, leftToDelete, rightToDelete, set, new StringBuilder());

        return new ArrayList<>(set);
    }

    private void dfs(String s, int idx, int leftCount, int leftToDelete, int rightToDelete, HashSet<String> set, StringBuilder sb) {
        if (idx == s.length()){
            if (leftToDelete == 0 && rightToDelete == 0 && leftCount == 0){
                set.add(sb.toString());
            }
            return;
        }
        char c = s.charAt(idx);
        if (c == '('){
            if (leftToDelete > 0){
                StringBuilder tmp = new StringBuilder(sb);
                dfs(s, idx + 1, leftCount, leftToDelete - 1, rightToDelete, set, tmp);
            }
            StringBuilder tmp = new StringBuilder(sb);
            tmp.append(c);
            dfs(s, idx + 1, leftCount + 1, leftToDelete, rightToDelete, set, tmp);
        }else if (c == ')'){
            if (rightToDelete > 0){
                StringBuilder tmp = new StringBuilder(sb);
                dfs(s, idx + 1, leftCount, leftToDelete,rightToDelete - 1, set, tmp);
            }
            if (leftCount > 0){
                StringBuilder tmp = new StringBuilder(sb);
                tmp.append(c);
                dfs(s, idx + 1, leftCount - 1, leftToDelete, rightToDelete, set, tmp);
            }
        }else {
            StringBuilder tmp = new StringBuilder(sb);
            tmp.append(c);
            dfs(s, idx + 1, leftCount, leftToDelete, rightToDelete, set, tmp);
        }
    }
}
